package leetcode.lcp0022;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	static int[] muls;

	static {
		muls = new int[7];
		muls[0] = 1;
		int mul = 1;
		for (int i = 1; i < 7; i++) {
			mul *= i;
			muls[i] = mul;
		}
	}

	public int c(int n, int m) {
		return muls[n] / (muls[m] * muls[n - m]);
	}

	public int paintingPlan(int n, int k) {
		if (k == 0) { // 这啥吖这是 case 48/53
			return 1;
		}
		if (k < n) {
			return 0;
		}
		int max = k / n;
		int ans = 0;
		for (int row = 0; row <= max && row < n; row++) {
			int rNum = row * n;
			int preCol = n - row;
			if (preCol == 0) {
				ans += c(n, row);
				continue;
			}
			int rest = k - rNum;
			if (rest % preCol != 0) {
				continue;
			}
			int cNum = rest / preCol;
			if (cNum == n) {
				continue;
			}
			ans += c(n, row) * c(n, cNum);
		}
		if (k == n * n) {
			ans += 1;
		}
		return ans;
	}

	@Override
	public void debug4() {
		HelpDebug.compare(1, this.paintingPlan(1, 0));
		HelpDebug.compare(1, this.paintingPlan(2, 4));
		HelpDebug.compare(4, this.paintingPlan(2, 2));
		HelpDebug.compare(0, this.paintingPlan(2, 1));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
